#include "quicksort.h"
#include <iostream>
#include <stack>

using namespace std;


char check_sort(int listay[], int size)
{
	for(int i = 0; i < size - 1; i++){
		if (listay[i] <= listay [i+1])
			continue;
		else
		{
			printf("a[%d]: %d  a[%d]: %d\n",i,listay[i],i+1,listay[i+1]);
			return FALSE;
		}
	}
	return TRUE;
}

void norm_rec_quicksort (int list[], int m, int n)
{
    if( n - m  > 2 ){

		int k = choose_pivot(m,n);
        int piv = partition(list,k,m,n);

		norm_rec_quicksort(list,m,piv);
		norm_rec_quicksort(list,piv+1,n);
	}

}


void task_rec_quicksort (int list[], int m, int n)
{
    if( n - m  > 2 ){

		int k = choose_pivot(m,n);
        int piv = partition(list,k,m,n);
        #pragma omp parallel sections
        {
        #pragma omp section
		norm_rec_quicksort(list,m,piv);
        #pragma omp section
		norm_rec_quicksort(list,piv+1,n);
        }
    }

}

void data_rec_quicksort (int list[], int m, int n, int num_blocks)
{

    int block_sec = n / num_blocks;
	int** tmp = new int*[num_blocks];
    int i =0,j=0,k=0;

    // Create a 2D listay to hold the divided blocks for each listay
        for(j=0; j < num_blocks; j++)
        {
              tmp[j] = new int[block_sec];
            for(k=0; k < block_sec; k++)
            {
              if(k == n)
                  break;

              tmp[j][k] = list[i];
              i++;
        }
    }
    omp_set_num_threads(num_blocks);

    // int moo;
     int p;
    /*****  Threads for data decomposition ******/
    #pragma omp parallel for private(p)
    for(p=0;p<num_blocks; p++)
    {
        norm_rec_quicksort (tmp[p], m, block_sec);
     //   cout << " Thread number: "<< omp_get_thread_num() << " out of " << omp_get_num_threads() << " threads" <<endl; 
    }
     
    /********************************************/
    
    // ???Could possibly use threads for this too???
    merge_sort(tmp[0],tmp[1],list,tmp,block_sec,block_sec,n);
}


void comb_rec_quicksort (int list[], int m, int n, int num_blocks)
{

    int block_sec = n / num_blocks;
	int** tmp = new int*[num_blocks];
    int i =0,j=0,k=0;

    // Create a 2D listay to hold the divided blocks for each listay
        for(j=0; j < num_blocks; j++)
        {
              tmp[j] = new int[block_sec];
            for(k=0; k < block_sec; k++)
            {
              if(k == n)
                  break;

              tmp[j][k] = list[i];
              i++;
        }
    }
    omp_set_num_threads(num_blocks);

     //int moo;
     int p;
    /*****  Threads for data decomposition ******/
    #pragma omp parallel for private(p)
    for(p=0;p<num_blocks; p++)
    {
        task_rec_quicksort (tmp[p], m, block_sec);
       // cout << " Thread number: "<< omp_get_thread_num() << " out of " << omp_get_num_threads() << " threads" <<endl; 
    }
     
    /********************************************/
    
    // ???Could possibly use threads for this too???
    merge_sort(tmp[0],tmp[1],list,tmp,block_sec,block_sec,n);
}

//////////////////////// ITERATIVE FUNCTIONS ////////////////////////////

void norm_iter_quicksort (int list[], int m, int n)
{
    stack <int> s;
    s.push(m);
    s.push(n);
    while (!s.empty()) {

        int upper = s.top();
        s.pop();
        int lower = s.top();
        s.pop();
        if (upper - lower > 2){
        int p = choose_pivot(lower,upper);
        p = partition(list,p,lower,upper);

        s.push(p+1);
        s.push(upper);

        s.push(lower);
        s.push(p);
        }
}
 
}

void task_iter_quicksort (int list[], int m, int n)
{
        #pragma omp parallel sections
        {
        #pragma omp section
         norm_iter_quicksort (list,m,n);
        }
}



void data_iter_quicksort (int list[], int m, int n, int num_blocks)
{

    int block_sec = n / num_blocks;
	int** tmp = new int*[num_blocks];
    int i =0,j=0,k=0;

    // Create a 2D listay to hold the divided blocks for each listay
        for(j=0; j < num_blocks; j++)
        {
              tmp[j] = new int[block_sec];
            for(k=0; k < block_sec; k++)
            {
              if(k == n)
                  break;

              tmp[j][k] = list[i];
              i++;
        }
    }
    omp_set_num_threads(num_blocks);

    // int moo;
     int p;
    /*****  Threads for data decomposition ******/
    #pragma omp parallel for private(p)
    for(p=0;p<num_blocks; p++)
    {
        norm_iter_quicksort (tmp[p], m, block_sec);
     //   cout << " Thread number: "<< omp_get_thread_num() << " out of " << omp_get_num_threads() << " threads" <<endl; 
    }
     
    /********************************************/
    
    // ???Could possibly use threads for this too???
    merge_sort(tmp[0],tmp[1],list,tmp,block_sec,block_sec,n);
}


void comb_iter_quicksort (int list[], int m, int n, int num_blocks)
{

    int block_sec = n / num_blocks;
	int** tmp = new int*[num_blocks];
    int i =0,j=0,k=0;

    // Create a 2D listay to hold the divided blocks for each listay
        for(j=0; j < num_blocks; j++)
        {
              tmp[j] = new int[block_sec];
            for(k=0; k < block_sec; k++)
            {
              if(k == n)
                  break;

              tmp[j][k] = list[i];
              i++;
        }
    }
    omp_set_num_threads(num_blocks);

     //int moo;
     int p;
    /*****  Threads for data decomposition ******/
    #pragma omp parallel for private(p)
    for(p=0;p<num_blocks; p++)
    {
        task_iter_quicksort (tmp[p], m, block_sec);
       // cout << " Thread number: "<< omp_get_thread_num() << " out of " << omp_get_num_threads() << " threads" <<endl; 
    }
     
    /********************************************/
    
    // ???Could possibly use threads for this too???
    merge_sort(tmp[0],tmp[1],list,tmp,block_sec,block_sec,n);
}



////////////////////////////////////////////////////////////////////////


//////////////////////// EXTRA FUNCTIONS ///////////////////////////////
void swap (int *x, int *y)
{
	int temp;
	temp = *x;
	*x = *y;
	*y = temp;
}

int choose_pivot(int i, int j)
{
     return i + ((j - i)/2);
}

// Algorithm to merge the separate blocks of the data decomposition to the final sorted listay
void merge_sort(int *a, int *b,int *output,int **input, int size_a, int size_b,int n)
{
    
	int* list = new int[n];
    int i=0, j=0, k=0;
    static int count=0;
    
    if ( (size_a + size_b) <= n )
    {
        
        while( i < size_a && j < size_b)
        {

            if( a[i] < b[j] )
            {
                list[k] = a[i];
                ++i;
            }
            else
            {
                list[k] = b[j];
                ++j;
            }

        k++;

        }
            while( i < size_a){
                  list[k] = a[i];
                  ++i;
                  ++k;
            }

            while( j < size_b){
                  list[k] = b[j];
                  ++j;
                  ++k;
            }

        for(i=0; i<(size_a+size_b); i++){
         //   cout << list[i] << " " ;
            output[i] = list[i];
        }
       // cout << endl;

        count++;

        merge_sort(list,input[count+1],output,input,(size_a+size_b),size_b,n);
    }

    count =0;

}

// Partition function
//  -- Two pointers move towards the center until the left pointer finds an element greater than the pivot and the right finds an 
//        element less than the pivot.  The two elements are swapped, the pointers move in until they cross again, the pivot is
//          swapped into the position to which the right pointer opinrts and then the partition is complete
//
int partition(int list[], int p, int start, int end) {
    int l = start;
    int h = end - 2;
    int piv = list[p];
    swap1(list,p,end-1);

    while (l < h) {
        if (list[l] < piv) {
            l++;
        } else if (list[h] >= piv) { 
            h--;
        } else { 
            swap1(list,l,h);
        }
    }
    int idx = h;
    if (list[h] < piv) idx++;
    swap1(list,end-1,idx);
    return idx;
}

 void swap1(int list[], int i, int j) { 
    int temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}




////////////////////////////////////////////////////////////////////////


